package 环形链表II;

public class Solution {



    public ListNode detectCycle(ListNode head) {
        // 利用快慢指针进行推理,slow每次走一步,fast每次走两步
        // 1.存在环时，一定有fast == slow （fast相对于slow来说，是一步一步的追赶的）
        // 2.一定有： x + y = x + y + n( y + z )  => x = （ n - 1 ）（ y + z ） + z

        if ( head == null )
            return null;

        ListNode slow = head;
        ListNode fast = head;
        do{
            slow = slow.next;
            fast = fast.next;
            // fast 每次多走一步，当fast.next为null时，说明不存在环
            if ( fast != null )
                fast = fast.next;
        }while ( slow != fast && fast != null );
        if ( fast == null )
            return null;
        // 从相遇点开始，一个指针从头开始走(每次走一步)，一个指针从相遇点走（每次走一步），当两指针相遇的时候，即为环的入口
        ListNode findStart = head;
        while ( findStart != slow ){
            slow = slow.next;
            findStart = findStart.next;
        }
        return findStart;
    }
}